package cn.edu.sjtu;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import cn.edu.sjtu.dfa.*;

/**
 * Dealing with Data Flow Analysis, using GraphBuilder to get the predecessors of every instruction node.
 * @author Seabert
 *
 */
public class ReachingDefinition extends DataFlowAnalysis{
	private HashMap<String, Set<Integer>> definitions; //<variable name, instruction Index>
	private HashMap<Integer, String> index4definition;
	private GraphBuilder gb;
	private boolean inoutchanged;
	public ReachingDefinition(List<Instruction> list){
		super(list);
		
		if(list != null){
			
			definitions = new HashMap<String, Set<Integer>>();
			this.index4definition = new HashMap<Integer, String>();
			gb = new GraphBuilder(list);
			gb.buildGraph();
			gb.printPredecessors();
			inoutchanged = false;
						
		}
		else{
			System.out.println("Null Instruction List!");
		}
		
	}
	
	protected void calculateIn(int index){
		ArrayList<Integer> predecessors = gb.predecessors.get(index);
		Set<Integer> tmpIn = null;
		if(this.in.get(index) != null){
			tmpIn = this.in.get(index);
		}
		else{
			tmpIn = new TreeSet<Integer>();
			this.in.add(index, tmpIn);
		}
		Set<Integer> copyIn =(Set<Integer>) ((TreeSet<Integer>) tmpIn).clone();
		tmpIn.clear();
		for(Integer pre:predecessors){
			Set<Integer> outTmp = out.get(pre);
			if(outTmp != null){				
				tmpIn.addAll(outTmp);
			}
						
		}
		this.inoutchanged = !this.isSetEqual(tmpIn, copyIn);
	}
	
	protected void calculateOut(int index){
		Set<Integer> tmpIn = this.in.get(index);
		Set<Integer> tmpGen = this.gen.get(index);
		Set<Integer> tmpKill = this.kill.get(index);
		
		Set<Integer> tmpOut = this.out.get(index);
		Set<Integer> copyOut = (Set<Integer>)((TreeSet<Integer>)tmpOut).clone();
		tmpOut.clear();
		
		Set<Integer> tmp = (Set<Integer>)((TreeSet<Integer>)tmpIn).clone();
		
		tmp.removeAll(tmpKill);
		tmpOut.addAll(tmpGen);
		tmpOut.addAll(tmp);
		
		this.inoutchanged = !this.isSetEqual(copyOut, tmpOut);
		
		
	}
	
	protected void calculateGen(int index){
		int tmpType = GraphBuilder.getInstructionTypeNum(this.InstrList.get(index));
		if( tmpType == GraphBuilder.binop || tmpType == GraphBuilder.move || tmpType == GraphBuilder.pairmove || tmpType == GraphBuilder.callwithreturn){
			if(gen.get(index) != null){
				gen.get(index).add(index);
			}
			else{
				Set<Integer> tmp = new TreeSet<Integer>();
				tmp.add(index);
				gen.add(index, tmp);
			}
		}
	}
	protected void calculateKill(int index){
		int tmpType = GraphBuilder.getInstructionTypeNum(this.InstrList.get(index));
		String tmpName = this.index4definition.get(index);
		Set<Integer> tmpDef = this.definitions.get(tmpName);
		Set<Integer> tmpkill = null;
		if( tmpType == GraphBuilder.binop || tmpType == GraphBuilder.move || tmpType == GraphBuilder.pairmove || tmpType == GraphBuilder.callwithreturn){
			if(kill.get(index) != null){
				 tmpkill = kill.get(index);
				 tmpkill.addAll(tmpDef);
				 tmpkill.remove(index);
			}
			else{
				tmpkill = new TreeSet<Integer>();
				tmpkill.addAll(tmpDef);
				tmpkill.remove(index);
				gen.add(index, tmpkill);
			}
		}
	}
	
	public boolean isSetEqual(Set<Integer> set1, Set<Integer> set2){
		boolean isEqual = true;
		Iterator it1 = set1.iterator();
		Iterator it2 = set2.iterator();
		
		while(it1.hasNext() && it2.hasNext()){
			Integer i1 = (Integer) it1.next();
			Integer i2 = (Integer) it2.next();
			if(!i1.equals(i2)){
				isEqual = false;
				break;
			}
		}
		if(it1.hasNext() || it2.hasNext()){
			isEqual = false;
		}
		
		return isEqual;
	}
	
	private void calculateDefinitions(){
		for(int index = 0; index < this.InstrList.size(); index++){
			Instruction tmpInstr = this.InstrList.get(index);
			GraphBuilder.getInstructionTypeNum(tmpInstr);
			int tmpType = GraphBuilder.getInstructionTypeNum(tmpInstr);
			String variable = null;
			switch(tmpType){
			case GraphBuilder.binop:
				variable = "v"+((Binop)tmpInstr).getReturnRegister().getRegister();
				break;
			case GraphBuilder.move:
				DataContainer dc = ((Move)tmpInstr).getEnd();
				String type = dc.getClass().getName();
				if(type.equals("cn.edu.sjtu.dfa.Register")){
					variable = "v" + ((Register)dc).getRegister();
				}
				
				else if(type.equals("cn.edu.sjtu.dfa.ArrayValue")){
					variable = "array" + ((ArrayValue)dc).getArrayRef().getRegister() + "[v"+ ((ArrayValue)dc).getIndex().getRegister() +"]";
				}
				else if(type.equals("cn.edu.sjtu.dfa.ObjectValue")){
					variable = "object" + ((ObjectValue)dc).getArrayRef().getRegister() + "[v"+ ((ObjectValue)dc).getIndex().getRegister() +"]";
				}
				else{
					System.out.println("ERROR: Unresolved type:" + type);
				}
				break;
			case GraphBuilder.callwithreturn:						
				dc = ((CallWithReturn) tmpInstr).getMoveFunction().getEnd();
				type = dc.getClass().getName();
				if(type.equals("cn.edu.sjtu.dfa.Register")){
					variable = "v" + ((Register)dc).getRegister();
				}
				
				else if(type.equals("cn.edu.sjtu.dfa.ArrayValue")){
					variable = "array" + ((ArrayValue)dc).getArrayRef().getRegister() + "[v"+ ((ArrayValue)dc).getIndex().getRegister() +"]";
				}
				else if(type.equals("cn.edu.sjtu.dfa.ObjectValue")){
					variable = "object" + ((ObjectValue)dc).getArrayRef().getRegister() + "[v"+ ((ObjectValue)dc).getIndex().getRegister() +"]";
				}
				else{
					System.out.println("ERROR: Unresolved type:" + type);
				}
				break;
			}
			//System.out.println(variable);
			this.index4definition.put(index, variable);
			if(variable != null){
				
				if(this.definitions.containsKey(variable)){
					Set<Integer> tmp = this.definitions.get(variable);
					tmp.add(index);
				}
				else{
					Set<Integer> tmp = new TreeSet<Integer>();
					tmp.add(index);
					this.definitions.put(variable, tmp);
				}
			}
			
			
		}
		
	}
	private void printDefinitions(){
		if(this.definitions != null){
			Iterator it = this.definitions.entrySet().iterator();
			while(it.hasNext()){
				Entry entry = (Entry) it.next();
				System.out.print(entry.getKey() + " : ");
				Set<Integer> list = (Set<Integer>) entry.getValue();
				for(Integer inte: list){
					System.out.print(inte + " , ");
				}
				System.out.println();
			}
		}
		else{
			System.out.println("ERROR: null Definitions!");
		}
		System.out.println("+++++++++++++++++DEFINITIONS PRINT DONE++++++++++++++++++++++");
	}
	public void printIndex4Definition(){
		if(this.index4definition != null){
			Iterator it = this.index4definition.entrySet().iterator();
			while(it.hasNext()){
				Entry entry = (Entry) it.next();
				System.out.println(entry.getKey() + " : " + entry.getValue());
			}
		}
		else{
			System.out.println("ERROR: null index for definition!");
		}
		System.out.println("++++++++++++++++INDEX FOR DEFINITION PRINT DONE+++++++++++++++++++");
	}
	
	private void printSets(ArrayList<Set<Integer>> sets){
		Iterator it = sets.iterator();
		int index = 0;
		while(it.hasNext()){
			System.out.print(index++);
			System.out.print(" : ");
			Set<Integer> set = (Set<Integer>) it.next();
			Iterator setIt = set.iterator();
			while(setIt.hasNext()){
				System.out.print(setIt.next());
				System.out.print(", ");
			}
			System.out.println();
		}
		System.out.println("+++++++++++++++SET PRINT DONE++++++++++++++++++++");
	}
	public void Analysis(){
		this.calculateDefinitions();
		this.printDefinitions();
		this.printIndex4Definition();
		
		do{
			this.inoutchanged = false;
			for(int index = 0; index < this.InstrList.size(); index++){
				this.calculateGen(index);
				this.calculateKill(index);
				this.calculateIn(index);
				this.calculateOut(index);
			}
		}
		while(this.inoutchanged);
		
		System.out.println("GEN:");
		this.printSets(gen);
		System.out.println("KILL:");
		this.printSets(kill);
		System.out.println("IN:");
		this.printSets(in);
		System.out.println("OUT:");
		this.printSets(out);
		
	}
	

	public ArrayList<Instruction> getInstrList() {
		return InstrList;
	}

	public void setInstrList(ArrayList<Instruction> instrList) {
		InstrList = instrList;
	}

	public ArrayList<Set<Integer>> getGen() {
		return gen;
	}

	public void setGen(ArrayList<Set<Integer>> gen) {
		this.gen = gen;
	}

	public ArrayList<Set<Integer>> getKill() {
		return kill;
	}

	public void setKill(ArrayList<Set<Integer>> kill) {
		this.kill = kill;
	}

	public ArrayList<Set<Integer>> getIn() {
		return in;
	}

	public void setIn(ArrayList<Set<Integer>> in) {
		this.in = in;
	}

	public ArrayList<Set<Integer>> getOut() {
		return out;
	}

	public void setOut(ArrayList<Set<Integer>> out) {
		this.out = out;
	}
	
	public static void main(String args[]){
		Integer a = new Integer(1);
		Integer b = new Integer(1);
		System.out.println(a.equals(b));
		System.out.println(a.hashCode());
		System.out.println(b.hashCode());
		Set<Integer> set1 = new TreeSet<Integer>();
		Set<Integer> set2 = new TreeSet<Integer>();
		
		set1.add(1);
		set1.add(2);
		set2.add(1);
		set2.add(2);
		Set<Integer> set3 = (Set<Integer>)((TreeSet<Integer>)set2).clone();
		set2.add(3);
		
		DataFlowAnalyzer dfa = new DataFlowAnalyzer("Q:\\Temp\\", "C:\\TDDOWNLOAD\\courseware\\eclipse-jee-helios-win32\\eclipse\\workspace2\\Helloworld\\bin\\classes.dex");
		dfa.Analyse();
//		dfa.Print();
		ReachingDefinition gb = new ReachingDefinition(DataFlowAnalyzer.ils.get("sea.hello.HelloworldActivity").get("public ReachingDefinition()V"));
		gb.Analysis();
		System.out.println(gb.isSetEqual(set1, set2));
		System.out.println(gb.isSetEqual(set1, set3));
	}
	
}
